10717. Монетный завод

Канадский королевский завод производит столы, ножки которых составляют из монет. Каждый стол имеет четыре ножки, каждая ножка состоит из монет одного типа. Разные ножки состоят из разных типов монет. Например, одна ножка может состоять из четвертушек, другая – из десяток, третья – из одноцентовых, а четвертая – из двухцентовых монет. Имеется конечное количество типов монет. Количество монет каждого типа неограниченно. Известна толщина каждого типа монет. Необходимо определить максимально возможную высоту стола, не большую заданной величины и минимально возможную высоту стола, не меньшую заданной.

Вход. Состоит из нескольких тестов. Первая строка каждого теста содержит количество доступных номиналов монет n (4 £ n £ 50) и количество столов T (1 £ T £ 10), которое следует сделать. Следующие n строк характеризуют толщину имеющихся номиналов монет. Далее идут T строк, описывающие желаемые высоты столов, которые следует сконструировать. Последний тест содержит n = T = 0 и не обрабатывается.

Выход. Для каждой желаемой высоты стола вывести максимально возможную высоту стола, не большую желаемой и минимально возможную высоту стола, не меньшую желаемой.

Пример входа

4 2

50

100

200

400

1000

2000

0 0

Пример выхода

800 1200

2000 2000

РЕШЕНИЕ

НОК

Анализ алгоритма

Если a, b, c, d – толщины четырех типов монет, то минимально возможная высота стола, который можно сделать, равна h = НОК(a, b, c, d). Обозначим через low максимально возможную высоту стола, не большую желаемой величины Height. Тогда low должно делиться на h и быть максимально возможным значением, не большим Height. Отсюда

low = * h

Если вычисленное low равно Height (что возможно в случае, когда Height делится на h без остатка), то минимально возможная высота стола more, не меньшая Height, также равна Height. Иначе она равна low + h.

Остается перебрать все возможные четверки толщин номиналов монет и вычислить максимум среди всевозможных low и минимум среди всевозможных more.

Пример

Рассмотрим набор монет из первого теста, желаемая высота стола равна 1000. Имея 4 монеты с толщинами 50, 100, 200, 400 можно конструировать столы, высоты которых кратны НОК(50, 100, 200, 400) = 400. Искомые высоты столов, которые можно сделать, соответственно равны 800 и 1200.

Реализация алгоритма

Для решения задачи достаточно использовать целочисленный тип int. Поскольку на вход подается несколько тестов, читаем в цикле входные значения n и t, а также значения номиналов монет текущего теста в массив coins.

while(scanf("%d %d",&n,&t),n + t > 0)

{

for(i = 0; i < n; i++) scanf("%d",&coins[i]);

Для каждой прочитанной желаемой высоты стола Height применяем описанный выше алгоритм. Обозначим через Less максимум среди всевозможных low, а через Greater – минимум среди всевозможных more. Проинициализируем их.

while(t--)

{

scanf("%d",&Height);

Greater = 0x7FFFFFFF;

Less = 0;

Перебираем все возможные четверки номиналов монет x1 < x2< x3 < x4 (номиналы монет хранятся соответственно в coins[x1], coins[x2], coins[x3], coins[x4]).

for(x1 = 0; x1 < n - 3; x1++)

for(x2 = x1 + 1; x2 < n - 2; x2++)

for(x3 = x2 + 1; x3 < n - 1; x3++)

for(x4 = x3 + 1; x4 < n; x4++)

{

Вычисляем НОК толщин монет g = НОК(coins[x1], coins[x2], coins[x3], coins[x4]).

h = coins[x1] * coins[x2] / gcd(coins[x1],coins[x2]);

h = h / gcd(h,coins[x3]) * coins[x3];

h = h / gcd(h,coins[x4]) * coins[x4];

Для каждой четверки номиналов пересчитываем значения Less и Greater.

low = Height / h * h;

if (low > Less) Less = low;

if (low != Height) low += h;

if (low < Greater) Greater = low;

}

Выводим результат:

printf("%d %d\n",Less,Greater);

}

}